//leetcode第36题，经典回溯问题，套模板即可解决
#include <bits/stdc++.h>
using namespace std;
using vvint=vector<vector<int>>;
class Solution {
public:
    void dfs(vvint& ret,vector<int>& nums,int target,
        vector<int>& temp,int index,int pos)
    {
        if(pos==target)
        {
            ret.push_back(temp);
            return;
        }
        for(int i=index;i<nums.size();i++)
        {
            pos+=nums[i];
            if(pos>target)continue;
            temp.push_back(nums[i]);
            dfs(ret,nums,target,temp,i,pos);
            pos-=nums[i];
            temp.pop_back();
        }
    }
    vvint combinationSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vvint ret;
        vector<int> temp;
        dfs(ret,nums,target,temp,0,0);
        return ret;
    }
};
